#include <iostream>
#include <vector>
#include <random>
#include <string>
const int ASCII_RANGE=128;

int getCharIndex(const std::string& str,int k)
{
    if(k>=str.length())
        return 0;
    return str.at(k);
}

int getMaxLength(const std::vector<std::string>& strArr)
{
    int length=0;
    for(const std::string& x:strArr)
        if(length<x.length()) length=x.length();
    return length;
}

void radixSort(std::vector<std::string>& strArr)
{
    std::vector<std::string> sortedArr;
    sortedArr.resize(strArr.size());
    int maxLength=getMaxLength(strArr);
    for(int k=maxLength-1;k>=0;k--)
    {
        std::vector<int> count;
        count.resize(ASCII_RANGE);
        for(int i=0;i<strArr.size();i++)
        {
            int index=getCharIndex(strArr.at(i),k);
            count.at(index)++;
        }
        for(int i=1;i<count.size();i++)
        {
            count.at(i)=count.at(i)+count.at(i-1);
        }
        for(int i=strArr.size()-1;i>=0;i--)
        {
            int index=getCharIndex(strArr.at(i),k);
            int sortedIndex=count[index]-1;
            sortedArr.at(sortedIndex)=strArr.at(i);
            count.at(index)--;
        }
        strArr=sortedArr;
    }
}

int main()
{
    std::vector<std::string> arr={"qd","abc","qwe","hhh","a","cws","ope"};
    radixSort(arr);
    for(auto& i:arr)
        std::cout<<i<<' ';
    std::cout<<std::endl;
}